//xchg in d-list with sentinel
//2 situations (elements are near / elements are far)
//if you read this code, so soon I'll create the list-sort ^_^

#include <iostream>
#include <stdlib.h>
#include <iomanip> //for setw
using namespace std;


struct Elem
{
	Elem* next;
	Elem* prev;
	int value;
};

struct List
{
	Elem* head;
	Elem* tail;
	int len;
};
//I don't know how, but everything works fine without typedef
List* create_list()
{
	List* list = (List*) malloc (sizeof(List));
	list->head=0;
	list->len=0;
	return list;
}
Elem* create_elem(List* list, int val) //need list for testing about fill!!!
{
	Elem* elem = (Elem*) malloc (sizeof(Elem));
	elem->next=0;
	elem->value=val;
	//now will be dawn work with prev
	if (list->head!=0) //if list is not empty
	{
		elem->prev=list->tail; //set tail
		list->tail->next=elem; //connect with previos element
		list->tail=elem; 	//move tail
	}
	else //if list is empty
	{
		elem->prev=0;	//previous element not exist, then prev=NULL
		list->head=list->tail=elem;
	}
	return elem;
}
void append_to_begin(List* list, Elem* elem)	//as in s-list!
{
	elem->next=list->head;
	list->head=elem;
	list->len++;
}
void append_to_end(List* list, Elem* elem)	//very much better than in s-list!!!!!!!!!!!
{
	list->tail->next=elem;
	list->tail=elem;
	list->len++;
}
void insert_after(List* list, Elem* elem, int x)	//as in s-list, but it could be written differently
{
	Elem* d=list->head;
	for(int i=1;i<x;i++)	//go to x from head
		d=d->next;	//
	elem->next=d->next;
	d->next=elem;
	list->len++;
}
void print(List* list) //as in s-list!
{
	Elem* d=list->head;
	for(int i=1;i<=(list->len);i++)
	{
		cout<<setw(10)<<d->value;
		d=d->next;
	}
	cout<<endl;
	cout<<endl;
}
void give_freedom(List* list)	//as in s-list!
{
	Elem* d=0;
	for(int i=1;i<=list->len;i++)
	{
		d=list->head->next;
		free(list->head);
		list->head=d;
	}
	free(list);
}
///////////////////////////////////////////////////////////////

List* xchg(List* list, int a, int b)
{
	Elem* curr=list->head->prev; //sentinel
	Elem* min=list->head->prev; //sentinel
	Elem* precurr=0;
	Elem* postcurr=0;
	Elem* premin=0;
	Elem* postmin=0;
		
	for(int i=1; i<=a; i++)		//set curr and min from a and b
		curr=curr->next;
	for(int i=1; i<=b; i++)
		min=min->next;
	
	if (a>b)	//protection of fools
		{
			a+=b;
			b=a-b;
			a-=b;
		}
	
	if (abs(a-b)>1) //elements are far
	{
		precurr=curr->prev;
		postcurr=curr->next;
		premin=min->prev;
		postmin=min->next;
		
		precurr->next=min;	//8 changes of pointers
		postcurr->prev=min;
		premin->next=curr;
		postmin->prev=curr;
	
		curr->next=postmin;
		curr->prev=premin;
		min->next=postcurr;
		min->prev=precurr;
	}
	else	//elements are near
	{
		precurr=curr->prev;
		postmin=min->next;
		
		precurr->next=min;	//6 changes of pointers
		postmin->prev=curr;
		
		curr->next=postmin;
		curr->prev=min;
		min->next=curr;
		min->prev=precurr;
	}
	
	if (a==1)			// !!!!!!!!!!!!! head and tail recovery !!!!!!!!!!!!!!!
		list->head=min;		//I could not think of this for a long time:(
	if (b==list->len)		//
		list->tail=curr;	//

	return list;
}
int main()
{
	List* spisok=create_list();
	
	for(int i=2;i<=10000;i+=i)
	{
		Elem* d=create_elem(spisok, i);
		append_to_end(spisok, d);
	}
	
	Elem* sentinel = (Elem*) malloc (sizeof(Elem));	//creating the sentinel!
	sentinel->next=spisok->head;			//
	sentinel->prev=spisok->tail;			//
	sentinel->value=666;				//
	spisok->head->prev=sentinel;			//
	spisok->tail->next=sentinel;			//
	//cout<<spisok->head->prev->value<<endl; 	//look to sentinel!
	
	print(spisok);			
	
	spisok=xchg(spisok, 3, 5);
	
	print(spisok);
	//cout<<spisok->len<<endl;
	give_freedom(spisok);

	return 0;
}